package com.boot.leetcode;

import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * @Package com.boot.leetcode.editor
 */
public class BinaryTree {

    private int val;
    private BinaryTree left;
    private BinaryTree right;

    public BinaryTree(int val) {
        this.val = val;
    }

    public static void pre(BinaryTree tree){
        if(tree == null){
            return;
        }
        System.out.print(tree.val+" ");
        pre(tree.left);
        pre(tree.right);
    }

    public static void mind(BinaryTree tree){
        if(tree == null){
            return;
        }

        mind(tree.left);
        System.out.print(tree.val+" ");
        mind(tree.right);
    }

    public static void last(BinaryTree tree){
        if(tree == null){
            return;
        }
        last(tree.left);
        last(tree.right);
        System.out.print(tree.val+" ");
    }

    public static void level(BinaryTree tree){

        if(tree==null) {//空树
            return;
        }

        Queue<BinaryTree> queue=new LinkedList<>();
        queue.offer(tree);//offer方法表示添加元素到队尾
        while(!queue.isEmpty()) {
            BinaryTree temp=queue.poll();//poll方法删除队头元素
            System.out.print(temp.val+" ");
            if(temp.left!=null) {
                queue.offer(temp.left);
            }
            if(temp.right!=null) {
                queue.offer(temp.right);
            }
        }
    }

    /**
     * 层遍历   [[1], [2, 3], [4, 5, 6, 7]]
     */
    public static List<List<Integer>> levelInfo(BinaryTree root){
        List<List<Integer>> res =new ArrayList<>();
        if(root == null){
            return res;
        }

        List<BinaryTree> nodes=new ArrayList<>();
        nodes.add(root);
        while (!nodes.isEmpty()){
            int size =nodes.size();
            List<Integer> vals=new ArrayList<>();
            for (int i = 0; i < size; i++) {
                BinaryTree tmp = nodes.remove(0);
                vals.add(tmp.val);

                if(tmp.left !=null){
                    nodes.add(tmp.left);
                }
                if(tmp.right !=null){
                    nodes.add(tmp.right);
                }
            }
            res.add(vals);
        }
        return res;
    }

    public static List<List<Integer>> levelInfoN(NTreeNode root) {
        List<List<Integer>> res =new ArrayList<>();
        if(root == null){
            return res;
        }

        // 临时队列其实就是每一层的节点
        Queue<NTreeNode> temp = new LinkedList();
        temp.offer(root);

        while (!temp.isEmpty()){
            int size =temp.size();
            List<Integer> vals=new ArrayList<>();
            for (int i = 0; i < size; i++) {
                NTreeNode node=temp.poll();
                vals.add(node.val);
                if(!CollectionUtils.isEmpty(node.getChildren())){
                    temp.addAll(node.getChildren());
                }
            }
            res.add(vals);
        }
        return res;
    }

    /** 获取n层的节点 */
    public static LinkedList<Integer> getlevelN(BinaryTree root,int level,LinkedList<Integer> nums){

        if(nums == null){
            nums =new LinkedList<>();
        }

        if(level == 1){
            nums.addLast(root.val);
            return nums;
        }

        if(root.left !=null){
            getlevelN(root.left,level-1,nums);
        }

        if(root.right !=null){
            getlevelN(root.right,level-1,nums);
        }

        return nums;
    }

    public static void main(String[] args) {
        BinaryTree t1=new BinaryTree(1);

        BinaryTree t2=new BinaryTree(2);
        BinaryTree t3=new BinaryTree(3);
        t1.left=t2;t1.right=t3;

        BinaryTree t4=new BinaryTree(4);
        BinaryTree t5=new BinaryTree(5);
        t2.left=t4;t2.right=t5;

        BinaryTree t6=new BinaryTree(6);
        BinaryTree t7=new BinaryTree(7);
        t3.left=t6;t3.right=t7;

        BinaryTree.pre(t1);
        System.out.println("");
        BinaryTree.mind(t1);
        System.out.println("");
        BinaryTree.last(t1);
        System.out.println("");
        BinaryTree.level(t1);
        System.out.println("");
        List<List<Integer>> res= BinaryTree.levelInfo(t1);
        System.out.println(res);

        NTreeNode root=new NTreeNode(1);
        NTreeNode n1=new NTreeNode(2);
        NTreeNode n2=new NTreeNode(3);
        NTreeNode n3=new NTreeNode(4);
        List c1= Arrays.asList(new NTreeNode[]{n1,n2,n3});
        root.setChildren(c1);

        NTreeNode n4=new NTreeNode(5);
        NTreeNode n5=new NTreeNode(6);
        List c2 =Arrays.asList(new NTreeNode[]{n4,n5});
        n1.setChildren(c2);

        NTreeNode n7=new NTreeNode(7);
        NTreeNode n8=new NTreeNode(8);
        NTreeNode n9=new NTreeNode(9);

        List c3 =Arrays.asList(new NTreeNode[]{n7,n8,n9});
        n2.setChildren(c3);

        NTreeNode n10=new NTreeNode(10);
        NTreeNode n11=new NTreeNode(11);

        List c4 =Arrays.asList(new NTreeNode[]{n10,n11});
        n3.setChildren(c4);

        NTreeNode n12=new NTreeNode(12);
        NTreeNode n13=new NTreeNode(13);

        List c5 =Arrays.asList(new NTreeNode[]{n12,n13});
        n4.setChildren(c5);
        System.out.println("");
        System.out.println(levelInfoN(root));

        System.out.println("");
        LinkedList<Integer> n=getlevelN(t1,2,null);
        System.out.println(n);
    }
}
